package Preferred_algorithm.Topic7_Divide_and_conquer_algorithm;

public class merge_sort {

    //  912.排序数组
    //  https://leetcode.cn/problems/sort-an-array/

    int[] nums, tmp ;

    public int[] sortArray(int[] _nums) {
        nums = _nums;
        tmp = new int[nums.length];
        mergeSort(0, nums.length - 1);
        return nums;
    }

    public void mergeSort(int left ,int right) {
        if (left >= right) return;

        // 1. 根据中间点划分区间 [left, mid] [mid + 1 , right]
        int mid = (left + right) / 2;

        // 2. 先把左右区间排序
        mergeSort(left, mid);
        mergeSort(mid + 1, right);

        // 3. 合并两个有序数组

        int cur1 = left; // 遍历左区间
        int cur2 = mid + 1; // 遍历右区间
        int i = 0; // 遍历辅助数组

        while (cur1 <= mid && cur2 <= right) {
            tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];
            // 谁小辅助数组填谁，然后更新对应指针
        }

        //  cur1 , cur2 一定会有一个指针没有遍历到最后，处理这种情况
        while (cur1 <= mid) tmp[i++] = nums[cur1++];
        while (cur2 <= right) tmp[i++] = nums[cur2++];

        // 4. 还原
        for (int j = left; j <= right; j++)
            nums[j] = tmp[j - left];
        // 还原的过程中 , nums 不一定是从0开始计数, left 不一定为0，但是 tmp 一定是从0开始计数
    }
}
